/*Written by ZHANG JUN
 start date: 2000.5.24
 finish date:
*/
#include "common.h"
#include "stack.h"
#include "intqueue.h"
#include "stdio.h"
#include "alloc.h"

#define MAX_VERTEX_NUM 20

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
	char *str;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

Status CreateDG(ALGraph *pg)
{
 int i,k;
 int v1,v2;
 int slen;
 ArcNode *parc;
 char str[80];

 printf("\nPlease Input vexnum and arcnum:");
 scanf("%d,%d",&(pg->vexnum),&(pg->arcnum));

 for(i=0;i<pg->vexnum;i++)
 {
  printf("\nInput Vex NO.%d:\n",i+1);
  str[0]=0;
  get_str(str,80);
  slen=strlen(str);
  (pg->vertices[i]).str=(char *)malloc((slen+1)*sizeof(char));
  strcpy((pg->vertices[i]).str,str);
  pg->vertices[i].firstarc=NULL;
 }

 for(k=0;k<pg->arcnum;k++)
 {
  printf("\nInput NO.%d Arc:",k+1);
  scanf("%d,%d",&v1,&v2);
  v1--;v2--;
  parc=(ArcNode *)malloc(sizeof(ArcNode));
  parc->adjvex=v2;
  parc->nextarc=(pg->vertices[v1]).firstarc;
  (pg->vertices[v1]).firstarc=parc;
 }
 return OK;
}

void DFS(ALGraph *pg,Bool *visited,int v)
{
 ArcNode *parc;
 int w;

 visited[v]=TRUE;
 printf("\n%d:%s",v,(pg->vertices[v]).str);
 for(parc=(pg->vertices[v]).firstarc;parc;parc=parc->nextarc)
 {
  w=parc->adjvex;
  if(!visited[w])
   DFS(pg,visited,w);
 }
}

void DFSTraverse(ALGraph *pg)
{
 int v;
 Bool visited[MAX_VERTEX_NUM];

 for(v=0;v<pg->vexnum;v++)
  visited[v]=FALSE;
 for(v=0;v<pg->vexnum;v++)
  if(!visited[v])
   DFS(pg,visited,v);
}

void FindIndgree(ALGraph *pg,int *indegree)
{
 int i;
 ArcNode *parc;

 for(i=0;i<pg->vexnum;i++)
 {
  parc=(pg->vertices[i]).firstarc;
  while(parc)
  {
   indegree[parc->adjvex]++;
   parc=parc->nextarc;
  }
 }
}

Status TopologicalSort(ALGraph *pg,int *sarray)
{
 int *indegree;
 int i,j,k,count;
 ArcNode *parc;
 IntStack s;

 indegree=(int *)malloc((pg->vexnum)*sizeof(int));
 FindIndgree(pg,indegree);
 InitIntStack(&s,100);

 for(i=0;i<pg->vexnum;i++)
 {
  if(!indegree[i])
   PushInt(&s,i);
 }

 j=0;
 count=0;
 while(!IsIntStackEmpty(s))
 {
  PopInt(&s,&i);
  sarray[j++]=i;
  for(parc=(pg->vertices[i]).firstarc;parc;parc=parc->nextarc)
  {
   k=parc->adjvex;
   if(!(--indegree[k]))
    PushInt(&s,k);
  }
 }
 free(indegree);
 if(count<pg->vexnum)
  return ERROR;
 return OK;
}